#include <stdio.h>

// 这个题目的难点在于: 这不是单纯的找单身狗,他包含多个单独的数字
// 这个题目对补码和异或的机制要更熟悉,所以单纯理解是不能完全熟悉这一道题目的
// 对于两个在单独数字在数组来说: 异或出来的数字如果位上是1的,一定是两个数字位数不一样的地方
// 例如5和1来说:
// 5: 0101 1: 0001 
// 5^1: 0100 这里的第三位数的1就是两个不一样的位数的地方,且唯一
// 所以,在我们求数组两个单独出现的不同数字时
// 1.全部数字异或
// 2.位数上有1的部分为两个数字中一个其中一位上有1,且另外一个没有
// 3.位数上的1是所有该位上有1的数字,重复的异或后没有了,就剩下最后一个单独的结果

// 利用这个法则,我们就可以通过某一位来区分两个不重复的数字

void search (int array [] , size_t sz , int* num)
{

    int pos , ret ;

    for (int i = 0 ; i < sz ; i++)
    {

        ret ^= array [i] ;

    }

    for (pos = 0 ; pos < 32 ; pos++)
    {

        if (((ret >> pos) & 1) == 1 )
        {

            break ;

        }

    }

    for (int i = 0 ; i < sz ; i++)
    {

        if (((array [i] >> pos) & 1) == 1)
        {

            num [1] ^= array [i] ;

        }

        else
        {

            num [0] ^= array [i] ;

        }

    }

}

int main ()
{

    int array [] = {1 , 2 , 3 , 4 , 5 , 3 , 2 , 1} ;

    int number [2] = { 0 } ;

    size_t sz = sizeof (array) / sizeof (array [0]) ;

    search (array , sz , number) ;

    printf ("%d %d" , number [0] , number [1]) ;

    return 0 ;

}